class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ret(n + 1, 0);
        for(int i = 1, k = 1; i <= n; i++, k++)
        {
            int cnt = 0, tmp = i;
            while(tmp)
            {
                tmp &= tmp - 1;
                cnt++;
            }
            ret[k] = cnt;
        }
        return ret;
    }
};